; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

declare void @use(i8)

define i1 @mul_mask_pow2_eq0(i8 %x) {
; CHECK-LABEL: @mul_mask_pow2_eq0(
; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 44
  %and = and i8 %mul, 4
  %cmp = icmp eq i8 %and, 0
  ret i1 %cmp
}

; TODO: Demanded bits does not convert the mul to shift,
; but the 'and' could be of 'x' directly.

define i1 @mul_mask_pow2_ne0_use1(i8 %x) {
; CHECK-LABEL: @mul_mask_pow2_ne0_use1(
; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 40
; CHECK-NEXT:    call void @use(i8 [[MUL]])
; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 8
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 40
  call void @use(i8 %mul)
  %and = and i8 %mul, 8
  %cmp = icmp ne i8 %and, 0
  ret i1 %cmp
}

; negative test - extra use of 'and' would require more instructions

define i1 @mul_mask_pow2_ne0_use2(i8 %x) {
; CHECK-LABEL: @mul_mask_pow2_ne0_use2(
; CHECK-NEXT:    [[MUL:%.*]] = shl i8 [[X:%.*]], 3
; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 8
; CHECK-NEXT:    call void @use(i8 [[AND]])
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 40
  %and = and i8 %mul, 8
  call void @use(i8 %and)
  %cmp = icmp ne i8 %and, 0
  ret i1 %cmp
}

; non-equality predicates are converted to equality

define i1 @mul_mask_pow2_sgt0(i8 %x) {
; CHECK-LABEL: @mul_mask_pow2_sgt0(
; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 44
  %and = and i8 %mul, 4
  %cmp = icmp sgt i8 %and, 0
  ret i1 %cmp
}

; unnecessary mask bits are removed

define i1 @mul_mask_fakepow2_ne0(i8 %x) {
; CHECK-LABEL: @mul_mask_fakepow2_ne0(
; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 44
  %and = and i8 %mul, 5
  %cmp = icmp ne i8 %and, 0
  ret i1 %cmp
}

; non-zero cmp constant is converted

define i1 @mul_mask_pow2_eq4(i8 %x) {
; CHECK-LABEL: @mul_mask_pow2_eq4(
; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 44
  %and = and i8 %mul, 4
  %cmp = icmp eq i8 %and, 4
  ret i1 %cmp
}

; negative test - must be pow2 mask constant

define i1 @mul_mask_notpow2_ne(i8 %x) {
; CHECK-LABEL: @mul_mask_notpow2_ne(
; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 12
; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 12
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i8 %x, 60
  %and = and i8 %mul, 12
  %cmp = icmp ne i8 %and, 0
  ret i1 %cmp
}

define i1 @pr40493(i32 %area) {
; CHECK-LABEL: @pr40493(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AREA:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i32 %area, 12
  %rem = and i32 %mul, 4
  %cmp = icmp eq i32 %rem, 0
  ret i1 %cmp
}

define i1 @pr40493_neg1(i32 %area) {
; CHECK-LABEL: @pr40493_neg1(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 3
; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i32 %area, 11
  %rem = and i32 %mul, 4
  %cmp = icmp eq i32 %rem, 0
  ret i1 %cmp
}

define i1 @pr40493_neg2(i32 %area) {
; CHECK-LABEL: @pr40493_neg2(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 12
; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 12
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul i32 %area, 12
  %rem = and i32 %mul, 15
  %cmp = icmp eq i32 %rem, 0
  ret i1 %cmp
}

define i32 @pr40493_neg3(i32 %area) {
; CHECK-LABEL: @pr40493_neg3(
; CHECK-NEXT:    [[MUL:%.*]] = shl i32 [[AREA:%.*]], 2
; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
; CHECK-NEXT:    ret i32 [[REM]]
;
  %mul = mul i32 %area, 12
  %rem = and i32 %mul, 4
  ret i32 %rem
}

define <4 x i1> @pr40493_vec1(<4 x i32> %area) {
; CHECK-LABEL: @pr40493_vec1(
; CHECK-NEXT:    [[TMP1:%.*]] = and <4 x i32> [[AREA:%.*]], <i32 1, i32 1, i32 1, i32 1>
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[TMP1]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[CMP]]
;
  %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 12, i32 12>
  %rem = and <4 x i32> %mul, <i32 4, i32 4, i32 4, i32 4>
  %cmp = icmp eq <4 x i32> %rem, zeroinitializer
  ret <4 x i1> %cmp
}

define <4 x i1> @pr40493_vec2(<4 x i32> %area) {
; CHECK-LABEL: @pr40493_vec2(
; CHECK-NEXT:    [[MUL:%.*]] = mul <4 x i32> [[AREA:%.*]], <i32 12, i32 12, i32 12, i32 undef>
; CHECK-NEXT:    [[REM:%.*]] = and <4 x i32> [[MUL]], <i32 4, i32 4, i32 4, i32 4>
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[REM]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[CMP]]
;
  %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 12, i32 undef>
  %rem = and <4 x i32> %mul, <i32 4, i32 4, i32 4, i32 4>
  %cmp = icmp eq <4 x i32> %rem, zeroinitializer
  ret <4 x i1> %cmp
}

define <4 x i1> @pr40493_vec3(<4 x i32> %area) {
; CHECK-LABEL: @pr40493_vec3(
; CHECK-NEXT:    [[MUL:%.*]] = mul <4 x i32> [[AREA:%.*]], <i32 12, i32 12, i32 12, i32 12>
; CHECK-NEXT:    [[REM:%.*]] = and <4 x i32> [[MUL]], <i32 4, i32 4, i32 4, i32 undef>
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[REM]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[CMP]]
;
  %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 12, i32 12>
  %rem = and <4 x i32> %mul, <i32 4, i32 4, i32 4, i32 undef>
  %cmp = icmp eq <4 x i32> %rem, zeroinitializer
  ret <4 x i1> %cmp
}

define <4 x i1> @pr40493_vec4(<4 x i32> %area) {
; CHECK-LABEL: @pr40493_vec4(
; CHECK-NEXT:    [[MUL:%.*]] = mul <4 x i32> [[AREA:%.*]], <i32 12, i32 12, i32 12, i32 undef>
; CHECK-NEXT:    [[REM:%.*]] = and <4 x i32> [[MUL]], <i32 4, i32 4, i32 4, i32 undef>
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[REM]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[CMP]]
;
  %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 12, i32 undef>
  %rem = and <4 x i32> %mul, <i32 4, i32 4, i32 4, i32 undef>
  %cmp = icmp eq <4 x i32> %rem, zeroinitializer
  ret <4 x i1> %cmp
}

define <4 x i1> @pr40493_vec5(<4 x i32> %area) {
; CHECK-LABEL: @pr40493_vec5(
; CHECK-NEXT:    [[MUL:%.*]] = mul <4 x i32> [[AREA:%.*]], <i32 12, i32 12, i32 20, i32 20>
; CHECK-NEXT:    [[REM:%.*]] = and <4 x i32> [[MUL]], <i32 2, i32 4, i32 2, i32 4>
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[REM]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[CMP]]
;
  %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 20, i32 20>
  %rem = and <4 x i32> %mul, <i32 2, i32 4, i32 2, i32 4>
  %cmp = icmp eq <4 x i32> %rem, zeroinitializer
  ret <4 x i1> %cmp
}

define i1 @pr51551(i32 %x, i32 %y) {
; CHECK-LABEL: @pr51551(
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %t0 = and i32 %y, -7
  %t1 = or i32 %t0, 1
  %mul = mul nsw i32 %t1, %x
  %and = and i32 %mul, 3
  %cmp = icmp eq i32 %and, 0
  ret i1 %cmp
}

define i1 @pr51551_2(i32 %x, i32 %y) {
; CHECK-LABEL: @pr51551_2(
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %t0 = and i32 %y, -7
  %t1 = or i32 %t0, 1
  %mul = mul nsw i32 %t1, %x
  %and = and i32 %mul, 1
  %cmp = icmp eq i32 %and, 0
  ret i1 %cmp
}

define i1 @pr51551_neg1(i32 %x, i32 %y) {
; CHECK-LABEL: @pr51551_neg1(
; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], 4
; CHECK-NEXT:    [[T1:%.*]] = or i32 [[T0]], 1
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T1]], [[X:%.*]]
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %t0 = and i32 %y, -3
  %t1 = or i32 %t0, 1
  %mul = mul nsw i32 %t1, %x
  %and = and i32 %mul, 7
  %cmp = icmp eq i32 %and, 0
  ret i1 %cmp
}

define i1 @pr51551_neg2(i32 %x, i32 %y) {
; CHECK-LABEL: @pr51551_neg2(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[Y:%.*]], 1
; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP1]], 0
; CHECK-NEXT:    [[X_OP:%.*]] = and i32 [[X:%.*]], 7
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X_OP]], 0
; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[DOTNOT]], i1 true, i1 [[CMP1]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %t0 = and i32 %y, -7
  %mul = mul nsw i32 %t0, %x
  %and = and i32 %mul, 7
  %cmp = icmp eq i32 %and, 0
  ret i1 %cmp
}

define i32 @pr51551_demand3bits(i32 %x, i32 %y) {
; CHECK-LABEL: @pr51551_demand3bits(
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 7
; CHECK-NEXT:    ret i32 [[AND]]
;
  %t0 = and i32 %y, -7
  %t1 = or i32 %t0, 1
  %mul = mul nsw i32 %t1, %x
  %and = and i32 %mul, 7
  ret i32 %and
}
